package bTree.LeetCode;

import java.util.HashMap;
import java.util.Stack;

public class 重排链表2 {

    public class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }
    public void reorderList(ListNode head) {
        if (head.next==null){
            return;
        }
        HashMap<Integer,ListNode>hashMap=new HashMap<>();
        int cnt=1;
        ListNode p=head;
        while (p!=null){
            hashMap.put(cnt++, p);
            p=p.next;
        }
        int left=1,right=cnt-1;
        while (left<right){
            ListNode leftNode = hashMap.get(left);
            ListNode rightNode = hashMap.get(right);
            leftNode.next=rightNode;
            rightNode.next=hashMap.get(left+1);
            left++;
            right--;
        }
        if ((cnt-1)%2==1){
            hashMap.get(left+1).next=hashMap.get(left);
            ListNode listNode = hashMap.get(left);
            listNode.next=null;
        }else {
            ListNode listNode = hashMap.get(left);
            listNode.next=null;
        }
    }

}